package KmpAl;

import java.util.Arrays;

public class testal {
    public static void main(String[] args) {
//        String a = "abccclasdfjkabcdslkfjlasdjfassdfcabccccdccfc";
//        int[] next = kmpNext(a);
//        System.out.println(a);
//        for(int x: next){
//            System.out.print(x + "");
//        }
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        //String str2 = "BBC";

        int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));

        int index = kmpAl(str1, str2, next);
        System.out.println("index=" + index); // 15了


    }
    public static int kmpSearch(String str1, String str2, int[] next) {

        //遍历
        for(int i = 0, j = 0; i < str1.length(); i++) {

            //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点, 可以验证...
            while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j-1];
            }

            if(str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if(j == str2.length()) {//找到了 // j = 3 i
                return i - j + 1;
            }
        }
        return  -1;
    }
    public static int kmpAl(String s1,String s2,int[] next){

        for (int i = 0,j=0; i < s1.length(); i++){
            if(j > 0 && s1.charAt(i) != s2.charAt(j)){
                j = next[j-1];
            }
            if(s1.charAt(i) == s2.charAt(j)){
                j++;
            }

            if(j == s2.length()){
                return i - j + 1;
            }
        }

        return -1;
    }

    /**
     *
     * @param dest 把数组传进去
     * @return 生成next数组
     */
    public static  int[] kmpNext(String dest) {
        int next[] = new int[dest.length()];
        int j=0;
        for (int i = 1; i < next.length; i++ ){
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }else {
                j = 0;
            }
            next[i] = j;

        }
        return next;
    }


}
